switchable_cat

#SECCON_Beginners_2023 #crypto #Medium

reference

문제 코드

PATH: 'vault://data/SECCON_Beginners_2023/switchable_cat/problem.py'

기반의 암호화

예를 위해

위와 같은 식을 간단하게 6개 비트로 이루어진 평문을 암호화 한다고 했을 때

b = ((r >> 1) & 1) ^ \
    ((r >> 2) & 1) ^ \
    ((r >> 3) & 1)

이때의 난수 생성기에서 반환되는 n번째 난수의 초기 seed가

s e e d = s_{0} ∥ s_{1} ∥ s_{2} ∥ s_{3} ∥ s_{4} ∥ s_{5}

로 표현하면 다음과 같은 행렬식으로 연산을 표현할 수 있다.

(\begin{matrix} a_{n} \\ a_{n - 1} \\ a_{n - 2} \\ a_{n - 3} \\ a_{n - 4} \\ a_{n - 5} \end{matrix}) = {(\begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{matrix})}^{n} \cdot (\begin{matrix} s_{0} \\ s_{1} \\ s_{2} \\ s_{3} \\ s_{4} \\ s_{5} \end{matrix})

행렬곱은 sage 라이브러리를 이용하면 된다

PATH: 'vault://data/SECCON_Beginners_2023/switchable_cat/poc.sage'

행렬곱 생각 못함(제목 검색해 볼 껄...)
처음에 그냥 shift-xor암호화라고 생각해서 계산한게 실패 요인
1. shift-xor하면 정보 손실 일어난다고 생가해서 풀이 접근이 잘 못 되었다고 깨달았지만 행렬은 생각하지 못함